contents

프로세스 스케줄링은 운영체제(OS)의 핵심 기능으로, 특정 시점에 어떤 프로세스가 CPU를 사용할지 결정합니다. CPU가 하나인 시스템에서는 한 번에 하나의 프로세스만 실행할 수 있습니다. 스케줄러의 임무는 시스템이 반응성과 효율성을 유지하도록 이 시간 공유를 관리하는 것입니다.

비유하자면, CPU는 바쁜 주방의 헤드 셰프 1명이고, 프로세스들은 다양한 주문(애피타이저, 메인 요리, 디저트)입니다. 프로세스 스케줄러는 셰프가 다음으로 어떤 주문을 처리할지 순서를 정해주는 '작업 지시자(expediter)'와 같습니다.

프로세스 스케줄링의 목표

"최고의" 스케줄링 알고리즘은 달성하려는 목표에 따라 달라집니다. 주요 목표들은 종종 서로 상충 관계(trade-off)에 있습니다.

• CPU 이용률 극대화: CPU를 가능한 한 바쁘게 유지합니다. 처리할 작업이 있다면 CPU가 유휴 상태로 있지 않게 합니다.
• 처리량 극대화: 주어진 시간 동안 완료하는 프로세스(작업)의 수를 최대화합니다.
• 반환 시간 최소화: 프로세스가 제출된 시점부터 종료될 때까지 걸리는 총 시간을 최소화합니다.
• 대기 시간 최소화: 프로세스가 준비 큐(ready queue)에서 CPU를 기다리며 보낸 시간의 총합을 최소화합니다.
• 응답 시간 최소화: 대화형 시스템(PC나 스마트폰 등)에서 사용자의 명령과 시스템의 첫 번째 응답 사이의 시간을 최소화합니다. "빠릿빠릿한" 느낌을 주는 데 매우 중요합니다.
• 공정성 보장: 각 프로세스에 공정한 CPU 점유 시간을 할당하여, 특정 프로세스가 CPU 시간을 무기한 할당받지 못하는 기아 현상(starvation) 을 방지합니다.

스케줄러의 종류

OS는 종종 함께 작동하는 세 가지 유형의 스케줄러를 가집니다.

1. 장기 스케줄러 (작업 스케줄러): 디스크의 "작업 풀"에서 어떤 프로세스를 메모리의 준비 큐로 받아들일지 결정합니다. 드물게 실행되며 다중 프로그래밍 정도(메모리에 동시에 올라와 있는 프로세스의 수)를 제어합니다.
2. 단기 스케줄러 (CPU 스케줄러): 대부분의 사람들이 "스케줄러"라고 부르는 것입니다. 매우 빈번하게 실행되며, 준비 큐에서 프로세스를 선택하여 CPU에 할당합니다.
3. 중기 스케줄러 (스와퍼): 다중 프로그래밍 정도를 줄이고 메모리를 확보하기 위해 프로세스를 일시적으로 메모리에서 제거(디스크로 스와핑)하는 데 사용되기도 합니다.

선점형 vs. 비선점형

이는 스케줄링 전략 간의 가장 근본적인 구분입니다.

• 비선점형 스케줄링 (Non-Preemptive): 일단 프로세스에 CPU가 할당되면, 그 CPU를 강제로 빼앗을 수 없습니다. 해당 프로세스는 종료되거나, CPU를 자발적으로 포기할 때까지(예: 파일 읽기와 같은 I/O 작업을 기다릴 때) 실행됩니다. 이는 단순하지만, 긴 작업 하나가 전체 시스템을 멈추게 할 수 있습니다.
• 선점형 스케줄링 (Preemptive): OS가 실행 중인 프로세스를 강제로 중단시키고 CPU를 빼앗아 다른 프로세스에 할당할 수 있습니다. 이는 일반적으로 타이머 인터럽트에 의해 수행되어 모든 프로세스가 차례를 얻도록 보장합니다. 이는 응답성에 필수적이므로 모든 현대 운영체제(Windows, macOS, Linux, iOS)가 사용합니다.

🧠 주요 스케줄링 알고리즘

단순한 것부터 복잡한 것까지, 가장 잘 알려진 스케줄링 알고리즘은 다음과 같습니다.

선입 선출 (First-Come, First-Served, FCFS)

가장 단순한 스케줄링 알고리즘입니다. 은행 창구의 줄처럼 프로세스가 단순한 큐에 배치됩니다.

• 작동 방식: CPU를 가장 먼저 요청한 프로세스가 CPU를 먼저 받습니다.
• 종류: 비선점형.
• 장점: 매우 단순하고 구현하기 쉽습니다.
• 단점: 극도로 비효율적입니다. 하나의 긴 프로세스("호송대")가 뒤따르는 모든 짧은 프로세스들을 장시간 기다리게 만드는 호위 효과(Convoy Effect) 로 인해 평균 대기 시간이 매우 길어질 수 있습니다.

최단 작업 우선 (Shortest Job First, SJF)

전체적인 처리량을 향상시키기 위해 "가장 빨리 끝날" 작업을 우선시하는 알고리즘입니다.

• 작동 방식: 스케줄러는 준비 큐에서 예상 실행 시간이 가장 짧은 프로세스를 선택합니다.
• 종류: 비선점형(가장 짧은 작업을 완료까지 실행)이거나, 선점형(최소 잔여 시간 우선, SRTF)일 수 있습니다. SRTF는 새로 도착한 더 짧은 작업이 현재 작업을 중단시킬 수 있습니다.
• 장점: 평균 대기 시간을 최소화하는 데 최적임이 증명되었습니다.
• 단점:
  1. 기아 현상: 짧은 작업들이 계속 도착하면 긴 작업은 절대 실행되지 못할 수 있습니다.
  2. 비현실성: 미래의 실행 시간을 어떻게 알 수 있을까요? 보통 과거의 기록을 바탕으로 추정하는데, 이는 부정확할 수 있습니다.

우선순위 스케줄링 (Priority Scheduling)

각 프로세스에 우선순위(정수)를 할당하고, 가장 높은 우선순위를 가진 프로세스에 CPU를 할당합니다.

• 작동 방식: 가장 높은 우선순위의 프로세스를 선택합니다.
• 종류: 선점형 또는 비선점형일 수 있습니다. 높은 우선순위의 프로세스가 낮은 우선순위의 프로세스를 중단시킬 수 있습니다.
• 장점: 중요한 실시간 작업(예: 시스템 커널 프로세스)이 즉시 실행되도록 허용합니다.
• 단점: 기아 현상. 낮은 우선순위의 프로세스는 절대 실행되지 못할 수 있습니다. 이는 종종 에이징(Aging) 기법(오래 기다린 프로세스의 우선순위를 점진적으로 높여줌)으로 해결합니다.

라운드 로빈 (Round Robin, RR) ⏱️

고전적인 선점형 알고리즘이자 대부분의 현대 스케줄러의 기반입니다. 공정하고 응답성이 좋도록 설계되었습니다.

• 작동 방식: 선점형 FCFS입니다. 각 프로세스는 타임 슬라이스 또는 퀀텀(quantum)(예: 20 밀리초)이라고 불리는 작은 시간 단위를 할당받습니다.
  • 프로세스가 퀀텀이 만료되기 전에 완료되면, CPU를 포기합니다.
  • 퀀텀이 만료되면, OS는 강제로 프로세스를 중단시키고 준비 큐의 맨 뒤로 이동시킨 다음, 줄의 다음 프로세스에게 CPU를 할당합니다.
• 장점: 매우 공정하며(기아 현상 없음), 응답 시간이 뛰어나고, 구현이 간단합니다.
• 단점: 성능이 퀀텀 크기에 매우 의존적입니다.
  • 너무 크면: FCFS와 같아집니다.
  • 너무 작으면: OS가 문맥 교환(context switch) 에 너무 많은 시간을 소비하게 되며, 이는 순수한 오버헤드입니다.

핵심 개념

문맥 교환 (Context Switch)

문맥 교환은 선점형 스케줄링을 가능하게 하는 메커니즘입니다. OS가 현재 실행 중인 프로세스의 상태를 저장하고, 다음 프로세스의 상태를 불러오는(load) 과정입니다.

여기에는 다음 정보 저장이 포함됩니다.

• 프로그램 카운터 (다음 실행할 명령어)
• CPU 레지스터 값
• 메모리 관리 정보

이 과정은 순수한 오버헤드입니다. 즉, 문맥 교환 중에는 유용한 작업이 수행되지 않습니다. 좋은 스케줄러는 뛰어난 응답성을 제공하면서도 문맥 교환을 최소화합니다.

현대 스케줄러

어떤 현대 OS도 이 단순한 알고리즘 중 하나만 사용하지 않습니다. 일반적으로 다단계 피드백 큐(Multilevel Feedback Queue, MLFQ) 와 같은 조합을 사용합니다. 이 시스템은 여러 개의 큐를 사용하며, 각 큐는 다른 우선순위와 알고리즘을 가집니다(예: 높은 우선순위 큐는 작은 퀀텀의 RR을, 낮은 우선순위 큐는 큰 퀀텀의 RR을 사용). 이를 통해 OS는 대화형 작업에 매우 빠르게 반응하면서도, 오래 실행되는 백그라운드 작업에도 CPU 시간을 할당할 수 있습니다.

references